﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Brainee.Search
{
  /// <summary>
  /// Iterative deepening strategy uses a depth-limited strategy with increasing limits until a
  /// goal is found. 
  /// </summary>
  /// <remarks>
  /// It is complete, optimal for unit step costs, and has time complexity of
  /// O(b^d) and space complexity of O(bd).
  /// </remarks>
  public class IterativeDeepeningStrategy : ISearchStrategy
  {
    private uint _min;
    private uint _max;
    private uint _limit;
    private ILimitedSearchStrategy _strategy;
    IProblem _pb;

    public IterativeDeepeningStrategy (ILimitedSearchStrategy strategy)
      : this (strategy, 0, UInt32.MaxValue)
    {
    }

    public IterativeDeepeningStrategy (ILimitedSearchStrategy strategy, uint min, uint max)
    {
      _min = min;
      _max = max;
      _strategy = strategy;
    }

    public void Initialize (IProblem pb)
    {
      _limit = _min;
      _pb = pb;
      _strategy.Limit = _limit;
      _strategy.Initialize (_pb);
    }

    public bool HasUnexploredStates ()
    {
      return _strategy.HasUnexploredStates ();
    }

    public ISearchState NextState ()
    {
      if (!HasUnexploredStates ())
      {
        _limit++;
        if (_limit >= _max)
        {
          return null;
        }
        _strategy.Limit = _limit;
        _strategy.Initialize (_pb);
      }

      return _strategy.NextState ();
    }

    public void Expand (ISearchState node, IProblem pb)
    {
      _strategy.Expand (node, pb);
    }
  }
}
